//单词数组 words 的 有效编码 由任意助记字符串 s 和下标数组 indices 组成，且满足：words.length == indices.length
// 助记字符串 s 以 '#' 字符结尾
// 对于每个下标 indices[i] ，s 的一个从 indices[i] 开始、到下一个 '#' 字符结束（但不包括 '#'）的 子字符串 恰好与
//words[i] 相等
//
//
// 给你一个单词数组 words ，返回成功对 words 进行编码的最小助记字符串 s 的长度 。
//
//
//
// 示例 1：
//
//
//输入：words = ["time", "me", "bell"]
//输出：10
//解释：一组有效编码为 s = "time#bell#" 和 indices = [0, 2, 5] 。
//words[0] = "time" ，s 开始于 indices[0] = 0 到下一个 '#' 结束的子字符串，如加粗部分所示 "time#bell#"
//words[1] = "me" ，s 开始于 indices[1] = 2 到下一个 '#' 结束的子字符串，如加粗部分所示 "time#bell#"
//words[2] = "bell" ，s 开始于 indices[2] = 5 到下一个 '#' 结束的子字符串，如加粗部分所示 "time#bell#"
//
//
// 示例 2：
//
//
//输入：words = ["t"]
//输出：2
//解释：一组有效编码为 s = "t#" 和 indices = [0] 。
//
//
//
//
// 提示：
//
//
// 1 <= words.length <= 2000
// 1 <= words[i].length <= 7
// words[i] 仅由小写字母组成
//
//
// Related Topics 字典树 数组 哈希表 字符串 👍 311 👎 0


//? set判断尾部
function minimumLengthEncoding(words: string[]): number {
    /**
     * @param {string[]} words
     * @return {number}
     */
    let hashSet = new Set(words);
    for (let item of Array.from(hashSet)) {
        for (let i = 1; i < item.length; i++) {
            //? 切片，看看是否词尾在 hashSet 中，切片从1开始，只看每个单词的词尾
            let target = item.slice(i);
            //? 有则去掉
            hashSet.has(target) && hashSet.delete(target);
        }
    }
    let result = 0;
    //? 根据 hashSet 中剩余元素计算最终长度
    hashSet.forEach(item => result += item.length + 1)
    return result

};
//? 前缀树解法
function minimumLengthEncoding2(words: string[]): number {

    /*
     ? 当前单词是否属于某个单词的后缀 —> 单词倒序是否属于某个单词的前缀 —> 前缀树
     ? 对数组中的字符串我们可以预处理一下 : 根据单词长度进行排序，这样才能逐个判别子串
     ? 如果一个单词属于其他字符串的前缀，则不需要加上他的长度，否则 result += (单词长度＋1)
     */
    //? 前缀树
    let root = {};
    let result = 0;
    //? 处理一下数组，根据字符串长度排序
    words.sort((a,b)=>{
        return b.length-a.length;
    })

    //? 开始插入字符串，长的先插
    for(let word of words) {
        let flag = false;
        let cur = root;
        //? 单词倒叙：后缀 ——> 前缀
        for(let i = word.length - 1; i >= 0; i--) {
            let s = word[i];
            if(!cur[s]) {
                cur[s] = {};
                flag = true; //? 标记该元素不属于其他元素的后缀(/前缀/子字符串)
            }
            cur = cur[s];
        }
        if(flag) result += (word.length + 1);
    }
    return result;


};
